import java.util.ArrayList;

import org.apache.commons.lang.ArrayUtils;


public class Ex7_6 {

	String v;
	String w;
	
	// ver ex6_5_beta
	
	public Ex7_6() {
		ArrayList<String> inputs = Utils.readLines("C:\\Users\\josemfer\\Downloads\\input_7_6.txt");
		v = inputs.get(0);
		w = inputs.get(1);				
	}

	public static void main(String[] args) {
		Ex7_6 ex = new Ex7_6();
		
		//ex.getScore(v, w);
		//ex.getMiddleEdge(0,ex.v.length(),0,ex.w.length());
		//ex.linearSpace(0,ex.v.length(),0,ex.w.length());
		
		ex.linearSpace(0,2,0,1);
	}
	
	
	private void linearSpace(Integer top, Integer bottom, 
											Integer left, Integer right) {		
		
		//System.out.println("top=" + top + "  bottom=" + bottom + "   left=" + left + "  right="  + right);	
	
		
		if (left == right || top == bottom) {
			//System.out.println("top= " + top + "left= " + left);
			System.out.println("RETURN!!");
			return;
		}		
		Integer[][] mid = getMiddleEdge(top, bottom, left, right);		
		Integer midNode_i = mid[0][0];
		Integer midNode_j = mid[0][1];
		
		System.out.println("i=" + midNode_i + "  j=" + midNode_j);
		Integer direction = mid[1][0];		
		linearSpace(top,midNode_i,left,midNode_j);		
		
		
		  /*
		if (direction == 0 || direction == 1) {
			midNode_j += 1;			
		} else {
			midNode_i += 1;
		}
					
		linearSpace(midNode_i ,bottom,midNode_j,right);	 */
		
		
	}
	
	
	private Integer[][] getMiddleEdge(Integer top, Integer bottom, 
			Integer left, Integer right) {
		
		String v = this.v.substring(top,bottom);
		String w = this.w.substring(left,right);		
		
		Integer[] forw = getScore(v,w,w.length()/2)[0];			
		Integer[][] back = getScore(new StringBuilder(v).reverse().toString(),
				new StringBuilder(w).reverse().toString(),w.length()/2 );
	
		Integer[] backMiddle = back[0];
		Integer[] track = back[1];		
		ArrayUtils.reverse(backMiddle);
		ArrayUtils.reverse(track);		
		Integer i = getMax(forw, backMiddle);
		
		Integer[][] edge = new Integer[2][2];
		edge[0][0] =  i;
		edge[0][1] = w.length()/2;
		edge[1][0]  = track[i];
	
		//System.out.println();
		
		return edge;
		
		
	}

	private Integer getMax(Integer[] array1, Integer[] array2) {		
		Integer maxValue = -9999;
		Integer index = -1;
		if (array1.length != array2.length) {
			return null;
		}
		for (int i=0;i<array1.length;i++) {
			Integer sumVal = array1[i] + array2[i];
			if (sumVal > maxValue) {
				index = i;
				maxValue = sumVal;
			}
		}
		return index;
	}
	
	private Integer[][] getScore(String v, String w, Integer col) {
		Integer sigma = 5;
		String blosum62 = "ACDEFGHIKLMNPQRSTVWY";		
		Integer[][] blosumMatrix = 
				Utils.readMatrix("C:\\Users\\josemfer\\Downloads\\BLOSUM62.txt");
		
		Integer[] prevCol = new Integer[v.length()+1];
		Integer[] thisCol = new Integer[v.length()+1];	
		Integer[] track = new Integer[v.length()+1];	
		
		for (int j=0;j<=col;j++) {		
			prevCol = thisCol.clone();
			for (int i=0;i<=v.length();i++) {
				//System.out.println("i=" + i + "   j=" + j);
				if (j==0) {
					thisCol[i] = -i*sigma;
					track[i] = 0; 
				} else {
					if (i==0) {
						thisCol[i] = -j*sigma;								
					} else {						
						Integer up = thisCol[i-1] - sigma;
						Integer left = prevCol[i] - sigma;
						// get diagonal value
						char vi = v.charAt(i-1);
						char wj = w.charAt(j-1);
						Integer diag = prevCol[i-1] + 
								blosumMatrix[blosum62.indexOf(vi)][blosum62.indexOf(wj)];
						thisCol[i] = Utils.max(new Integer[]{left,diag, up});
						track[i] = Utils.maxIndex(new Integer[]{left,diag, up});						
					}					
				}				
			}						
		}		
		Integer[][] matrix = new Integer[2][prevCol.length];
		matrix[0] = thisCol;
		matrix[1] = track;
			
		return matrix;	
	} // end getScore

} // end class
